1. Field of the Invention
The present invention relates to a communication system employing Low-Density Parity Check (LDPC) codes as error-correcting codes. More particularly, the present invention relates to a channel encoding/decoding apparatus and method using LDPC codes, the block lengths of which are variable.
2. Description of the Related Art
In wireless communication systems, link performance is degraded by various kinds of noise and fading phenomena, Inter-Symbol Interference (ISI), etc. Therefore, in order to implement high-speed digital communication systems requiring high data throughput and reliability, such as next-generation communication systems, digital broadcasting systems, and portable Internet services, it is essential to develop technology for overcoming noise, fading, and ISI. Research has been conducted to provide error-correcting codes to efficiently restore information distortion and improving communication reliability.
LDPC codes were first reported by Gallager in the 1960's but were not further investigated because, in view of the state of the art at that time, they were too complex to be implemented. However, as turbo codes, which were discovered by Berrou, Glavieux, and Thitimajshima in 1993, provide performance approaching the Shannon's channel capacity limit, there have been many interpretations of their performance and characteristics, and research on channel encoding based on iterative decoding and graphs has been then pursued. Upon this opportunity, the LDPC codes have been restudied in the late 1990's, and finally have been proven to have performance close to the Shannon's channel capacity limit when decoding is performed by applying iterative decoding based on sum-product algorithms on Tanner graphs. A Tanner graph is a special type of factor graph.
The LDPC codes are typically represented using graph representations, and many characteristics of the LDPC codes can be analyzed through methods based on graph theories, algebra, and probability theories. In general, graph representations of channel codes are not only useful for code descriptions, but can also derive natural decoding algorithms because each of intra-graph vortexes corresponding to information on encoded bits and each of intra-graph edges corresponding to relations between the encoded bits may be regarded as a communication network where the respective bits exchange messages through the respective edges. Examples of decoding algorithms derived from trellis that may be considered a type of graph include the conventional Viterbi algorithm and the Bahl, Cocke, Jelinek and Raviv (BCJR) algorithm.
An LDPC code is generally defined by a parity check matrix, and may be represented using a bipartite graph called a Tanner graph. The bipartite graph refers to a graph in which vortexes constituting the graph are divided into two different types of vortexes, and the LDPC code is represented by a bipartite graph including one set of vortexes called variable nodes and the other set of vortexes called check nodes. The variable nodes correspond one-to-one to encoded bits.
Hereinafter, a graph representation of a conventional LDPC code will be described with reference to FIGS. 1 and 2.
FIG. 1 illustrates an exemplary parity check matrix H1 of a conventional LDPC code, including four rows and eight columns. Referring to FIG. 1, the fact that the parity check matrix includes eight columns means that the LDPC code is an LDPC code for generating a codeword of length 8, and the respective columns correspond to encoded eight bits.
FIG. 2 illustrates a Tanner graph corresponding to H1 of a conventional LDPC code.
Referring to FIG. 2, the Tanner graph of the conventional LDPC code includes eight variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216, and four check nodes 218, 220, 222, 224. Here, an ith column and a jth row of the parity check matrix H1 of the LDPC code correspond to a variable node xi and a jth check node respectively. In addition, a value of 1 at an intersection of the ith column and the jth row of the parity check matrix H1 of the LDPC code, that is, a non-zero value, means that there is an edge between the variable node xi and the jth check node on the Tanner graph, as illustrated in FIG. 2.
In the tanner graph of the LDPC code, the degree of each of the variable and check nodes refers to the number of edges connected to each node, and is equal to the number of non-zero entries in a column or row of the parity check matrix of the LDPC code, corresponding to the relevant node. In FIG. 2, for example, the degrees of the variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216 are 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and the degrees of the check nodes 218, 220, 222, and 224 are 6, 5, 5, and 5, respectively. In addition, the numbers of non-zero entries in the respective columns of the parity check matrix H1 of FIG. 1, corresponding to the variable nodes of FIG. 2, coincide with the above degrees of 4, 3, 3, 3, 2, 2, 2, and 2, in order, and the numbers of non-zero entries in the respective rows of the parity check matrix H1 of FIG. 1, corresponding to the check nodes of FIG. 2, coincide with the above degrees of 6, 5, 5, and 5, in order.
In order to represent a degree distribution for nodes of an LDPC code, fi denotes the ratio of the number of variable node of degree i to the total number of variable nodes, and gi denotes the ratio of the number of check node of degree j to the total number of check nodes. For example, in the case of the LDPC code according to FIGS. 1 and 2, f2=4/8, f3=3/8, f4=1/8, and fi=0 for i≠2, 3, 4, and g5=3/4, g6=1/4, and gj=0 for j≠5, 6. If the length of the LDPC code, that is, the number of columns, is N, and the number of rows is N/2, the density of non-zero entries in the overall parity check matrix having the above degree distribution is calculated by the following equation:
                                                        2              ⁢                              f                2                            ⁢              N                        +                          3              ⁢                              f                3                            ⁢              N                        +                          4              ⁢                              f                4                            ⁢              N                                            N            ·                          N              /              2                                      =                  5.25          N                                    (        1        )            
In Equation (1), the density of non-zero entries having a value of 1 continues to decrease as N increases. In general, since the density of non-zero entries is inversely proportional to the code length N of an LDPC code, the density of non-zero-entries is very low when N is large. The term “low-density” in the term LDPC originated as a result of the above relationship.
Reference will now be made to the characteristics of a parity check matrix of a conventional LDPC code, with reference to FIG. 3. FIG. 3 illustrates a conventional LDPC code adopted as standard technology in the Digital Video Broadcasting-Satellite Second Generation (DVB-S2). DVB-S2 is a European digital broadcasting standard.
Referring to FIG. 3, N, denotes an LDPC codeword length, K1 denotes an information word length, and (N1−K1) denotes a parity length. Integers M1 and q are determined in such a manner as to satisfy (N1−K1)/M1=q. With regard to this, K1/M1 must also be an integer. For the convenience of explanation, the parity check matrix of FIG. 3 will be referred to as a first parity check matrix H1.
Referring to FIG. 3, the structure of the parity part in the parity check matrix, that is, columns K1 to (N1−1), is in the form of a dual diagonal structure. Thus, the degree distribution of all columns included in the parity part has a value of 2, except for the last column having a value of 1.
The structure of the information word part in the parity check matrix, that is, columns 0 to (K1−1), is established according to the following rules:
<Rule 1>: K1 columns corresponding to an information word are grouped into column groups each including M1 columns to generate K1/M1 column groups. A way to construct each column belonging to each column group follows Rule 2 as described below.
<Rule 2>: First, a position of 1 in the 0th column of each ith column group (i=0, 1, . . . , K1/M1−1) is determined. Here, Di denotes the degree of the 0th column of each ith column group. Assuming that row positions including an entry of 1 in the 0th column of each ith column group are Ri,0(1), Ri,0(2), . . . , Ri,0(Di), row positions including an entry of 1 in a jth column of an ith column group, Ri,k(k) (k=1, 2, . . . , Di), are defined by the following equation:Ri,j(k)=Ri,(j-1)(k)+q mod (N1−K1),k=1,2, . . . ,Di,i=0,1 . . . ,K1/M1−1,j=1,2, . . . ,M1−1  (2)
According to Rule 2, all columns belonging to an ith column group (i=0, 1, . . . , K1/M1−1) have a constant degree of Di.
LDPC codes designed based on the above rules can be efficiently encoded using a structured form. However, the DVB-S2 standard employing such LDPC codes has disadvantages in that only two block lengths of LDPC codes are used due to limitations on using the LDPC codes, as well as in that different parity check matrices for supporting the two block lengths must be stored.
Next, a description will be given of individual steps of an LDPC encoding procedure using the aforementioned DVB-S2 parity check matrix.
In the following description, for the convenience of explanation, information word bits of length K1 will be designated by (i0, i1, . . . , iK1-1), and parity bits of length N1−K1 will be designated by (p0,p1, . . . , pN1-K1-1). An LDPC code to be described in detail below is characterized by N1=16200, K1=10800, M1=360, and q=15.
Step 1: Parity bits are initialized: p0=p1= . . . =pN1-K1-1=0.
Step 2: Information on row positions including an entry of 1 in the first column of the first column group is fetched from stored parity check matrix information:R1,0(1)=0,R1,0(2)=2084,R1,0(3)=1613,R1,0(4)=1548,R1,0(5)=1286,R1,0(6)=1460,R1,0(7)=3196,R1,0(8)=4297,R1,0(9)=2481,R1,0(10)=3369,R1,0(11)=3451,R1,0(12)=4620,R1,0(13)=2622.
Using the fetched information and the information bit i0, specific parity bits px are updated as given in the following equation. Here, x denotes the value of each R1,0(k), k=1, 2, . . . , 13:p0=p0⊕i0,p2084=p2084⊕i0,p1613=p613⊕i0,p1548=p1548⊕i0,p1286=p1286⊕i0,p1460=p1460⊕i0,p3196=p3196⊕i0,p4297=p4297⊕i0,p2481=p2481=p2481⊕i0,p3369=p3369⊕i0,p3451=p3451⊕i0,p4620=p4620⊕i0,p2622=p2622⊕i0.  (3)
In Equation (3), px=px⊕i0 may be expressed by px←px⊕i0, and ⊕ denotes binary addition.
Step 3: For the next 359 information word bits i1, i2, . . . , i359 following i0, values defined by the following equation are first obtained:{x+(m mod M1)×q} mod(N1−K1),M1=360,m=1,2, . . . ,359  (4)
In Equation (4), x denotes the value of each R1,0(k), k=1, 2, . . . , 13. It is to be noted that Equation (4) is conceptually the same expression as Equation (2).
Next, a similar operation to Equation (3) is performed using the values obtained by Equation (4). That is, for im, parity bits p{x+(m mod M1)×q} mod(N1-K1) are updated. For m=1 (i.e. i1), for example, parity bits p{x+(m mod M1)×q} mod(N1-K1) are updated as given in the following equation:p15=p15⊕i0,p2099=p2099⊕i0,p1628=p1628⊕i0,p1563=p1563⊕i0,p1301=p1301⊕i0,p1475=p1475⊕i0,p3211=p3211⊕i0,p4312⊕p4312⊕i0,p2496=p2496⊕i0,p3384=p3384⊕i0,p3466=p3466⊕i0,p4635=p4635⊕i0,p2637=p2637⊕i0.  (5)
It is to be noted that q=15 in the case of Equation (5). Such an operation is also performed for m=1, 2, . . . , 359 in the same manner.
Step 4: In the same manner as in step 2, for the 361th information word bit i360, information on R2,0(k)(k=1, 2, . . . , 13) is fetched, and specific parity bits px are updated. Here, x denotes R2,0(k). For the next 359 information word bits i361, i362, . . . , i719 following i360, parity bits p{x+(m mod M1)×q} mod(N1-K1) (m=361, 362, . . . , 719) are updated by applying Equation (4).
Step 5: For all 360 information word bit groups, steps 2, 3 and 4 are repeated respectively. Finally, parity bits are determined by the following equation:pi=pi⊕i−1,i=1,2, . . . , N1−K1−1  (6)
In Equation (6), parity bits pi are parity bits for which LDPC encoding is completed.
As mentioned above, encoding in the DVB-S2 is conducted through steps 1 to 5.
In order to apply LDPC codes as described above to a real world communication system, they must be designed in such a manner to be appropriate for a data transfer rate required by the communication system. More particularly, in adaptive communication systems employing Hybrid Automatic Retransmission reQuest (HARQ) schemes and Adaptive Modulation and Coding (AMC) schemes, as well as communication systems supporting various broadcast services, LDPC codes having various block lengths are needed to support various data transfer rates demanded by users.
However, in the case of the aforementioned LDPC code used in the DVB-S2 system, not only there are only two block lengths due to limited use of the LDPC code, but also independent parity check matrices are needed for the two respective block lengths.
When available block lengths are limited as mentioned above, there is a problem in that it is difficult to enhance the extensibility and flexibility of a system.
In addition, storing all the parity check matrices corresponding to the respective block lengths of the LDPC code causes a problem of memory efficiency degradation.